[51nod1518]-稳定多米诺覆盖

容斥原理, 插头dp

我们发现恰好 k 条线不被跨过很难搞，但是至少 k 条线不被跨过就可以 dp，想到容斥（二项式反演）。

同时枚举行和列的复杂度太高，但是枚举一维后，另一维就可以 dp 了。

我们选择枚举列，行做 dp：

  • f[i, j] 表示 i 行 j 列恰好填满的方案数（插头dp预处理），
  • g[k] 表示至少 k 条列线，0 条行线的方案数（0 条行线 通过容斥实现）

注意：这里插头dp 轮廓线 和回路计数的不太一样

（所以要就题论题的设计轮廓线啊！！！）

重点总结：1. 想到容斥 2. 想到枚举一维后 dp 另一维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int mod = 1e9 + 7;
typedef long long ll;
int n, m;
ll dp[2][1 << 16], f[20][20], ans, g[20], row[20];
vector<int> vec;

void calc(int lim) {
    memset(dp, 0, sizeof(dp));
    int tot = (1 << lim) - 1, p = 1;
    dp[0][tot] = 1;
    rep(i, 1, n) {
        rep(j, 1, lim) {
            memset(dp[p], 0, sizeof(dp[p]));
            rep(s, 0, tot) {
                if (!((s >> (lim - 1)) & 1)) {
                    (dp[p][(s << 1 | 1) & tot] += dp[p ^ 1][s]) %= mod;  // 竖放一块 
                } else {
                    if (!(s & 1) && j > 1)
                        (dp[p][(s << 1 | 3) & tot] += dp[p ^ 1][s]) %= mod;  // 横放一块
                    (dp[p][(s << 1) & tot] += dp[p ^ 1][s]) %= mod;  // 不放
                }
            }
            p ^= 1;
        }
        f[i][lim] = dp[p ^ 1][tot];
    }
}

void prework() {
    rep(i, 1, m) calc(i);
}

int main() {
    n = m = 16;
    prework();
    while (cin >> n >> m) {
        ans = 0;
        rep(s, 1 << (m - 1), (1 << m) - 1) {
            vec.clear();
            int lst = 0;
            rep(i, 1, m)
                if ((s >> (i - 1)) & 1) vec.push_back(i - lst), lst = i;
            rep(i, 1, n) {
                row[i] = 1;
                for (int j = 0; j < vec.size(); j++)
                    (row[i] *= f[i][vec[j]]) %= mod;
            }
            rep(i, 1, n) {
                g[i] = row[i];
                rep(j, 1, i - 1)
                    (g[i] -= row[i - j] * g[j] % mod) %= mod;
            }
            if ((vec.size()) & 1) (ans += g[n]) %= mod;
            else (ans -= g[n]) %= mod;
        }
        printf("%lld\n", (ans + mod) % mod);
    }
    return 0;
}